package com.yanceysong.codetop.s61_s70;

import com.yanceysong.common.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class S70_Easy_144_二叉树的前序遍历 {
    /**
     * .S70_Easy_144_二叉树的前序遍历
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/binary-tree-preorder-traversal/">LeetCode 144. 二叉树的前序遍历</a>
     * .<p>
     * .【题目描述】
     * .给你二叉树的根节点 root，返回它节点值的 前序 遍历。前序遍历访问顺序：根节点 -> 左子树 -> 右子树。
     * .<p>
     * .【核心标签】二叉树 / 深度优先搜索 DFS / 迭代遍历 / Morris遍历
     * .<p>
     * .【示例 1】
     * .输入：root = [1,null,2,3]
     * .结构：
     * .     1
     * .      \
     * .       2
     * .      /
     * .     3
     * .输出： [1,2,3]
     * .<p>
     * .【示例 2】输入：root = [] 输出：[]
     * .【示例 3】输入：root = [1] 输出：[1]
     * .【示例 4】输入：root = [1,2,3] 输出：[1,2,3]
     * .<p>
     * .=============================================
     * .【三种方法对比】
     * .1. 递归：最直观，实现简单。时间O(n)，空间O(h)（递归栈）
     * .2. 迭代（显式栈）：模拟系统调用栈，适合避免递归栈溢出。时间O(n)，空间O(h)
     * .3. Morris遍历：利用线程化二叉树思想，时间O(n)，空间O(1)，不额外使用栈，但会临时修改指针（遍历结束后复原）。
     * .<p>
     * .【ASCII 遍历流程示例 - 迭代法】
     * .树：
     * .     1
     * .    / \
     * .   2   3
     * .  / \   \
     * . 4  5    6
     * .栈变化 (push时显示)：
     * .初始：nodeStack=[]
     * .push 1 -> [1] 输出:1
     * .右3入栈, 左2入栈 -> [3,2]
     * .pop 2 输出:2 -> push 5, push 4 -> [3,5,4]
     * .pop 4 输出:4
     * .pop 5 输出:5
     * .pop 3 输出:3 -> push 6 -> [6]
     * .pop 6 输出:6
     * .最终输出：[1,2,4,5,3,6]
     * .<p>
     * .【Morris 前序步骤示例】（核心是“建立和拆除临时线索”）
     * .设当前节点 cur，有左子树：
     * .1. 找到左子树中最右节点 pre（前驱）。
     * .2. 若 pre.right == null：建立 pre.right = cur，并【访问 cur】然后 cur = cur.left。
     * .3. 若 pre.right == cur：说明左子树已处理完，撤销线索 pre.right = null，cur = cur.right。
     * .4. 若 cur.left == null：直接访问 cur，然后 cur = cur.right。
     * .指针临时改变：
     * .        cur
     * .       /   \
     * .     L       R
     * . L 的最右节点 pre 其 right 指针暂时指向 cur，形成一条可返回路径。
     * .<p>
     * .【关键洞察】
     * .- 前序遍历访问顺序固定：根 -> 左 -> 右。
     * .- 迭代实现的栈入栈顺序需注意：先压右后压左，保证左子树先弹出。
     * .- Morris 利用“前驱节点”构造返回路径，从而节省栈空间。
     * .- Morris 遍历会临时修改树结构，适合只读后不再使用原指针结构的场景；并发/不可变树不适用。
     * .<p>
     * .【复杂度分析】
     * .- 所有方法时间复杂度均为 O(n)，每个节点恰好访问一次。
     * .- 递归与迭代空间复杂度 O(h)，h 为树高度，最坏（链状）退化为 O(n)。
     * .- Morris 空间复杂度 O(1)。
     * .<p>
     * .【扩展】
     * .- 若需要同时返回节点深度，可在遍历时传入 depth 参数或使用辅助结构。
     * .- 三序列统一框架：调整 "访问节点" 的时机即可得到前/中/后序。
     */

    // ===================== 递归实现 =====================
    public List<Integer> preorderTraversal(TreeNode rootNode) {
        List<Integer> preorderResult = new ArrayList<>();
        traversePreOrder(rootNode, preorderResult);
        return preorderResult;
    }

    private void traversePreOrder(TreeNode currentNode, List<Integer> preorderResult) {
        if (currentNode == null) {
            return; // 递归基：空节点
        }
        // 前序：先访问根
        preorderResult.add(currentNode.val);
        // 再访问左子树
        traversePreOrder(currentNode.left, preorderResult);
        // 最后访问右子树
        traversePreOrder(currentNode.right, preorderResult);
    }

    // ===================== 迭代实现（显式栈） =====================

    public List<Integer> preorderTraversalIterative(TreeNode rootNode) {
        List<Integer> preorderResult = new ArrayList<>();
        if (rootNode == null) {
            return preorderResult;
        }
        Deque<TreeNode> nodeStack = new ArrayDeque<>();
        nodeStack.push(rootNode);
        while (!nodeStack.isEmpty()) {
            TreeNode currentNode = nodeStack.pop();
            preorderResult.add(currentNode.val); // 根 -> 左 -> 右
            // 注意压栈顺序：右先压，左后压 => 左子节点更早被弹出处理
            if (currentNode.right != null) {
                nodeStack.push(currentNode.right);
            }
            if (currentNode.left != null) {
                nodeStack.push(currentNode.left);
            }
        }
        return preorderResult;
    }

    // ===================== Morris 前序遍历（O(1) 额外空间） =====================

    public List<Integer> preorderTraversalMorris(TreeNode rootNode) {
        List<Integer> preorderResult = new ArrayList<>();
        TreeNode cur = rootNode;
        while (cur != null) {
            if (cur.left == null) {
                // 无左子树：直接访问 + 走向右子树
                preorderResult.add(cur.val);
                cur = cur.right;
            } else {
                // 找左子树最右节点（前驱）
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    // 第一次到达：访问当前节点，建立线索回退路径
                    preorderResult.add(cur.val);
                    pre.right = cur;      // 建立临时线索
                    cur = cur.left;       // 下潜左子树
                } else {
                    // 第二次到达：左子树已处理完，撤销线索
                    pre.right = null;     // 恢复原结构
                    cur = cur.right;      // 转向右子树
                }
            }
        }
        return preorderResult;
    }

    // ===================== 测试用例 =====================

    public static void main(String[] args) {
        S70_Easy_144_二叉树的前序遍历 solution = new S70_Easy_144_二叉树的前序遍历();
        System.out.println("=== 二叉树前序遍历测试开始 ===");

        // 测试1：空树
        System.out.println("\n--- 测试1: 空树 ---");
        TreeNode root1 = null;
        testAllMethods(solution, root1, List.of());

        // 测试2：单节点
        System.out.println("\n--- 测试2: 单节点 ---");
        TreeNode root2 = new TreeNode(10);
        testAllMethods(solution, root2, List.of(10));

        // 测试3：只有左子链
        System.out.println("\n--- 测试3: 左链 1->2->3->4 ---");
        TreeNode root3 = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(3,
                                new TreeNode(4), null), null), null);
        testAllMethods(solution, root3, List.of(1, 2, 3, 4));

        // 测试4：只有右子链
        System.out.println("\n--- 测试4: 右链 1->2->3->4 ---");
        TreeNode root4 = new TreeNode(1, null,
                new TreeNode(2, null,
                        new TreeNode(3, null,
                                new TreeNode(4))));
        testAllMethods(solution, root4, List.of(1, 2, 3, 4));

        // 测试5：完全二叉树 (1,2,3,4,5,6,7)
        System.out.println("\n--- 测试5: 完全二叉树 ---");
        TreeNode root5 = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4), new TreeNode(5)),
                new TreeNode(3,
                        new TreeNode(6), new TreeNode(7)));
        testAllMethods(solution, root5, List.of(1, 2, 4, 5, 3, 6, 7));

        // 测试6：不完全二叉树（带缺失与多层）
        System.out.println("\n--- 测试6: 不完全二叉树 ---");
        TreeNode root6 = new TreeNode(8,
                new TreeNode(3,
                        new TreeNode(1), new TreeNode(6,
                        new TreeNode(4), new TreeNode(7))),
                new TreeNode(10, null,
                        new TreeNode(14,
                                new TreeNode(13), null)));
        testAllMethods(solution, root6, List.of(8, 3, 1, 6, 4, 7, 10, 14, 13));

        // 测试7：根含左右孩子
        System.out.println("\n--- 测试7: 根含左右孩子 ---");
        TreeNode root7 = new TreeNode(5, new TreeNode(2), new TreeNode(9));
        testAllMethods(solution, root7, List.of(5, 2, 9));

        // 测试8：含重复值
        System.out.println("\n--- 测试8: 含重复值 ---");
        TreeNode root8 = new TreeNode(1,
                new TreeNode(1,
                        new TreeNode(1), null),
                new TreeNode(1,
                        null, new TreeNode(1)));
        testAllMethods(solution, root8, List.of(1, 1, 1, 1, 1));

        // 测试9：不平衡深度差异
        System.out.println("\n--- 测试9: 不平衡树 ---");
        TreeNode root9 = new TreeNode(10,
                new TreeNode(5,
                        new TreeNode(2,
                                new TreeNode(1), null), null),
                new TreeNode(15));
        testAllMethods(solution, root9, List.of(10, 5, 2, 1, 15));

        // 测试10：随机树一致性验证（迭代 / 递归 / Morris）
        System.out.println("\n--- 测试10: 随机树一致性 (50轮) ---");
        java.util.Random rand = new java.util.Random(144);
        for (int t = 1; t <= 50; t++) {
            TreeNode randomRoot = buildRandomTree(rand, 12, 0.6); // 至多12节点，60%概率生孩子
            List<Integer> a = solution.preorderTraversal(randomRoot);
            List<Integer> b = solution.preorderTraversalIterative(randomRoot);
            List<Integer> c = solution.preorderTraversalMorris(randomRoot);
            if (!a.equals(b) || !b.equals(c)) {
                System.out.println("随机树第" + t + "轮遍历结果不一致:" + a + " vs " + b + " vs " + c);
                throw new AssertionError("遍历结果不一致");
            }
        }
        System.out.println("✓ 随机树一致性全部通过");

        // 测试11：长左链（深度 100）验证递归与迭代性能及栈行为
        System.out.println("\n--- 测试11: 长左链 深度100 ---");
        TreeNode longLeft = new TreeNode(1);
        TreeNode p = longLeft;
        for (int i = 2; i <= 100; i++) {
            p.left = new TreeNode(i);
            p = p.left;
        }
        List<Integer> expectLeft = new ArrayList<>();
        for (int i = 1; i <= 100; i++) expectLeft.add(i);
        testAllMethods(solution, longLeft, expectLeft);

        // 测试12：长右链（深度 100）
        System.out.println("\n--- 测试12: 长右链 深度100 ---");
        TreeNode longRight = new TreeNode(1);
        p = longRight;
        for (int i = 2; i <= 100; i++) {
            p.right = new TreeNode(i);
            p = p.right;
        }
        List<Integer> expectRight = new ArrayList<>();
        for (int i = 1; i <= 100; i++) expectRight.add(i);
        testAllMethods(solution, longRight, expectRight);

        // 测试13：稀疏树（大量空孩子）
        System.out.println("\n--- 测试13: 稀疏树 ---");
        TreeNode sparse = new TreeNode(10,
                new TreeNode(5,
                        null, new TreeNode(9,
                        new TreeNode(8), null)),
                new TreeNode(20,
                        null, new TreeNode(30)));
        testAllMethods(solution, sparse, List.of(10, 5, 9, 8, 20, 30));

        System.out.println("\n=== 所有测试完成 ===");
    }

    // ===================== 辅助测试方法与随机树生成 =====================

    private static void testAllMethods(S70_Easy_144_二叉树的前序遍历 solution, TreeNode root, List<Integer> expected) {
        List<Integer> recursive = solution.preorderTraversal(root);
        List<Integer> iterative = solution.preorderTraversalIterative(root);
        List<Integer> morris = solution.preorderTraversalMorris(root);
        System.out.println("递归:   " + recursive);
        System.out.println("迭代:   " + iterative);
        System.out.println("Morris: " + morris);
        System.out.println("期望:   " + expected);
        assert recursive.equals(expected) : "递归结果不匹配";
        assert iterative.equals(expected) : "迭代结果不匹配";
        assert morris.equals(expected) : "Morris结果不匹配";
        assert recursive.equals(iterative) && iterative.equals(morris) : "三种实现结果不一致";
        System.out.println("✓ 测试通过");
    }

    private static TreeNode buildRandomTree(java.util.Random rand, int maxNodes, double growProb) {
        if (maxNodes <= 0) return null;
        TreeNode root = new TreeNode(rand.nextInt(50));
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int count = 1;
        while (!queue.isEmpty() && count < maxNodes) {
            TreeNode node = queue.poll();
            // 随机生成左子
            if (rand.nextDouble() < growProb && count < maxNodes) {
                node.left = new TreeNode(rand.nextInt(50));
                queue.offer(node.left);
                count++;
            }
            // 随机生成右子
            if (rand.nextDouble() < growProb && count < maxNodes) {
                node.right = new TreeNode(rand.nextInt(50));
                queue.offer(node.right);
                count++;
            }
        }
        return root;
    }
}
